package main.java.com.itlin.datastructure.binarysearchtree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BSTTree1 {

    public BSTNode root;//根节点

    public static class BSTNode{
        public int key;
        Object value;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }

    /**
     * 查找关键字对应的值
     * @param key - 关键字
     * @return 关键字对应的值
     */
    public Object get(int key){
        return doGet(root, key);
    }

    private Object doGet(BSTNode node, int key){
        if(node == null){
            return null; // 找不到
        }
        if(key < node.key){
            return doGet(node.left, key); // 向左找
        }else if(key > node.key){
            return doGet(node.right, key); // 向右找
        }else{
            return node.value; // 找到
        }

    }

    /**
     * 非递归方式实现查找关键字对应的值
     * @param key - 关键字
     * @return 关键字对应的值
     */
    public Object get2(int key){
        BSTNode node = root;
        while(node != null){
            if(key < node.key){
                node = node.left; // 向左找
            }else if(key > node.key){
                node  = node.right; // 向右找
            }else {
                return node.value; // 找到了
            }
        }
        return null;

    }

    /**
     * 查找最小关键字对应的值  找最左边的 左叶子节点
     * @return 关键字对应的值
     */
    public Object min(){
        return min(root);
    }

    private Object doMin(BSTNode node){
        if (node == null) return null; // 找不到
        if(node.left == null){
            return node.value; // 找到最小值
        }else {
            return doMin(node.left); // 向左找
        }
    }

    /**
     * 查找最小关键字对应的值  非递归实现
     * @return
     */
    public Object min2(){
        if (root == null) return null;
        BSTNode p = root;
        while(p.left != null){
            p = p.left;
        }
        return p.value;
    }

    /**
     * 查找最大关键字对应的值   找最右边的叶子节点 递归方法
     * @return 关键字对应的值
     */
    public Object max(){
        return max(root);
    }

    private Object doMax(BSTNode node){
        if (node == null) return null;
        if (node.right == null){
            return node.value;
        }else {
            return doMax(node.right);
        }
    }

    /**
     * 查找最大关键字对应的值   非递归实现
     * @return
     */
    public Object max2(){
        if (root == null) return null;
        BSTNode p = root;
        while (p.right != null){
            p = p.right;
        }
        return p.value;
    }

    /**
     * 存储关键字和对应的值
     * @param key
     * @param value
     */
    public void put(int key, Object value){

        BSTNode node = root;
        BSTNode parent = null;
        // 1. key 有   更新
        while(node != null){
            parent = node;
            if(key < node.key){
                node = node.left; // 向左找
            }else if(key > node.key){
                node  = node.right; // 向右找 4 -> 7 -> 8 -> null
            }else {
                //找到了 key 更新
                node.value = value;
                return ;
            }
        }
        // 父节点 parent
        if (parent == null){
            root = new BSTNode(key, value);
            return;
        }
        // 2. key 没有 新增
//      new BSTNode(key, value);
        if (key < parent.key){
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * 查找关键字的前驱值 （比当前元素小的 最大值）
     * @param key - 关键字
     * @return 前驱值
     */
    //二叉搜索树的中序遍历结果就是从小到大的顺序
    /*
       * 1.节点有左子树，此时前驱节点就是左子树的最大值
       * 2.节点没有左子树，若离它最近的祖先从左而来，此祖先即为先驱
     */
    public Object successor(int key){
        // 1. 找到关键字对应的节点
        BSTNode p = root;
        //自左而来的祖先
        BSTNode ancestorFromLeft = null;
        while(p != null){
            if(key < p.key){
                p = p.left; // 继续向左找
            }else if (key > p.key){
                ancestorFromLeft = p; // 离它最近的祖先从左而来，此祖先即为后继
                p = p.right; // 继续向右找
            }else {
                break;
            }
        }
        //p 就是查找到的节点
        if(p == null) return null;
        /*
         * 情况1.节点有左子树，此时前驱节点就是左子树的最大值
         * 情况2.节点没有左子树，若离它最近的祖先从左而来，此祖先即为先驱
         */
        // 2. 判断节点是否有左子树，如果有左子树，返回左子树的最大值
        //情况1.节点有左子树，此时前驱节点就是左子树的最大值
        if (p.left != null){
            return max(p.left);
        }
        //情况2.节点没有左子树，若离它最近的祖先从左而来，此祖先即为先驱
        return ancestorFromLeft != null ? ancestorFromLeft.value : null;
    }

    private Object max(BSTNode node){
        if (node == null) return null;
        while (node.right != null){
            node = node.right;
        }
        return node.value;
    }

    /**
     * 查找关键字的后继值 （比当前元素大的最小值）
     * @param key - 关键字
     * @return 后继值
     */
    /*
     * 情况1.节点有右子树，此时后继节点就是右子树的最小值
     * 情况2.节点没有右子树，若离它最近的祖先从右而来，此祖先即为后继
     */
    public Object predecessor(int key){
        // 1. 找到关键字对应的节点
        BSTNode p = root;
        //自左而来的祖先
        BSTNode ancestorFromRight = null;
        while(p != null){
            if(key < p.key){
                ancestorFromRight = p; // 离它最近的祖先从左而来，此祖先即为后继
                p = p.left; // 继续向左找
            }else if (key > p.key){
                p = p.right; // 继续向右找
            }else {
                break;
            }
        }
        //p 就是查找到的节点
        if(p == null) return null;
        /*
         * 情况1.节点有右子树，此时后继节点就是右子树的最小值
         * 情况2.节点没有右子树，若离它最近的祖先从右而来，此祖先即为后继
         */
        //情况1.节点有右子树，此时后继节点就是右子树的最小值
        if (p.right != null){
            return min(p.right);
        }
        //情况2.节点没有右子树，若离它最近的祖先从右而来，此祖先即为后继
        return ancestorFromRight != null ? ancestorFromRight.value : null;
    }

    public Object min(BSTNode node){
        if(node == null) return null;
        BSTNode p = node;
        while(p.left != null){
            p = p.left;
        }
        return p.value;
    }

    /**
     * 根据关键字删除
     * @param key - 关键字
     * @return 被删除关键字对应的值  （只删除一个元素）
     */
    /*
     * 删除操作有四种情况
     * 1. 删除的节点没有左子节点，直接将右子节点连接给 父节点
     * 2. 删除的节点没有右子节点，直接将左子节点连接给 父节点
     * 3. 删除的节点左右子节点都没有，已经被涵盖在 1. 2. 中， 直接将null 连接给 父节点
     * 4. 删除的节点左右子节点都有，找到后继节点，将后继节点（S）链接给 父节点（SP），此时又分为两种情况
     * 4.1 SP 就是被删除节点， 此时 D和S紧邻， 只需将S 链接给Parent即可
     * 4.2 SP不是被删除节点，此时 D和S不紧邻， 需要将s的后代 链接给 SP，再将 S 链接给 Parent
     */
    public Object delete(int key){
        // 1.不管是情况几都要先找到要删除的节点，如果找不到，则返回null
        //定义 节点指针
        BSTNode p = root;
        //定义 父节点指针
        BSTNode parent = null;
        //通过循环比较 查找节点
        while(p != null){
            if(key < p.key){
                parent = p;
                p = p.left;
            }else if(key > p.key){
                parent = p;
                p = p.right;
            }else {
                break;
            }
        }
        // 再次判断是否找到节点， 因为又可能是 循环结束 而非找到
        if(p == null) return null;
        // 2. 找到节点后，判断节点是否有左右子树
        // 2.3 删除的节点左右子节点都没有，已经被涵盖在 1. 2. 中， 直接将null 连接给 父节点
        // 2.1 删除的节点没有左子节点，直接将右子节点连接给 父节点
        if(p.left == null ){
            //删除节点
            shift(parent, p, p.right);
        }// 2.2 删除的节点没有右子节点，直接将左子节点连接给 父节点
        else if(p.right == null){
            //删除节点
            shift(parent,p, p.left);
        }// 2.4 删除的节点左右子节点都有，找到后继节点，将后继节点（S）链接给 父节点（SP），此时又分为两种情况
        else{
            //情况4
            // 4.1 找到被删除节点的后继值
            /*
             * 因为  当前要删除节点在情况4中有左右子树， 所以后继节点只需要找到右子树的最小值即可
             */
            //定义指针，从删除节点的右子节点开始
            BSTNode s = p.right;
            //定义后继节点的父亲
            BSTNode sparent = p;
            while(s.left != null){
                sparent = s;
                s = s.left;
            }// s 即为后继节点
            // 4.2 处理后继值的 后事
            if (sparent != p){
                // 4.2.1 SP不是被删除节点，此时 D和S不紧邻， 需要将s的后代 链接给 SP，再将 S 链接给 Parent
                shift(sparent,s,s.right);//顶上去的一定是 右子节点  因为左子节点更小，不可能有左孩子
                s.right = p.right;

            }
            // 4.2.2 SP 就是被删除节点， 此时 D和S紧邻， 只需将S 链接给Parent即可SP不是被删除节点，此时 D和S不紧邻， 需要将s的后代 链接给 SP，再将 S 链接给 Parent
            // 4.3 后继值取代被删除的节点
            shift(parent, p, s);
            s.left = p.left;
        }
        return p.value;
    }

    /**
     * 托孤方法， 将子节点连接到父节点
     * @params: parent - 被删除节点的父亲
     * @params: deleted - 被删除节点
     * @params: child - 被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child){
        //如果删除的节点没有父节点，直接将子节点设置成 根节点
        if(parent == null) root = child;
        else if (deleted == parent.left) parent.left = child;
        else parent.right = child;
    }

    /**
     * 根据关键字删除
     * @param key - 关键字
     * @return 被删除关键字对应的值  （只删除一个元素）
     */
    public Object deleteRecur(int key){
        ArrayList<Object> result = new ArrayList<>();//保存被删除节点的值
        root = doDelete(root, key,result);
        return result.isEmpty() ? null : result.get(0);
    }
    /**
     * 定义递归方法
     * node 删除起点
     * 返回值是 删除节点的 子节点 或 null
     */
    private BSTNode doDelete(BSTNode node , int key, ArrayList<Object> result){
        //不管是什么递归方法， 先写返回值的出口
        if(node == null) return null;
        // 1, 找到要删除的节点
        if(key < node.key) {
            node.left = doDelete(node.left, key,result);
            return node;
        }
        if(key > node.key) {
            node.right = doDelete(node.right, key,result);
            return node;
        }
        result.add(node.value);
        // 情况1 - 只有右孩子
        if(node.left == null) return node.right;
        // 情况2 - 只有左孩子
        if(node.right == null) return node.left;
        // 情况3 - 左右孩子都有
        // 3.1 找到后继节点
        //3.1.1 后继节点和当前节点相邻
        BSTNode s = node.right;
        while(s.left != null){
            s = s.left;
        }

        // 3.1.2 后继节点和当前节点不相邻
        // 删除后继节点
        s.right = doDelete(node.right, s.key,result);
        // 3.2 将后继节点链接给当前节点
        s.left = node.left;
        return s;
    }

    // 中序遍历过程中即可得到 升序遍历的结果 可以进行 各种条件 的判断

    /**
     * 将比关键字小的值返回到集合中
     * @param key
     * @return
     */
    public List<Object> less(int key){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty()){
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BSTNode pop = stack.pop();
                if(pop.key < key) result.add(p.value);
                p = pop.right;
            }
        }

        return result;


    }


    /**\
     * 找到 > key 的所有 value
     * @param key
     * @return
     */
    public List<Object> greater(int key){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty()){
            if (p != null) {
                stack.push(p);
                p = p.right;
            }else {
                BSTNode pop = stack.pop();
                if(pop.key > key){
                    result.add(pop.value);
                }else{
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }


    /**
     * 找到 >= key1 且 <= key2 的所有 value
     * @param key1
     * @param key2
     * @return
     */
    public List<Object> between(int key1, int key2){
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while(p != null || !stack.isEmpty()){
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BSTNode pop = stack.pop();
                if(pop.key >= key1 && pop.key <= key2) {
                    result.add(pop.value);
                }else if(pop.key > key2){
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }



}
